# Definition for singly-linked list.
"""
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

"""
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dimhead = ListNode(0)
        dimhead.next = head
        i, node = self.removenode(dimhead, n)
        return node.next

    def removenode(self, head, n):
        if not head.next:
            return 1, head
        i = self.removenode(head.next, n)
        if i[0] == n:
            head.next = i[1].next
        return i[0] + 1, head

    def removeNthFromEnd_opt(self,head,n):
        fast = head
        i = 0
        while i < n and fast:
            fast = fast.next
            i += 1
        slow = head
        while fast.next:
            fast = fast.next
            slow = slow.next
            if not fast.next:
                slow.next = slow.next.next
        return head

a1 = ListNode(1)
a2 = ListNode(2)
a3 = ListNode(3)
a4 = ListNode(4)
a5 = ListNode(5)
a1.next = a2
a2.next = a3
a3.next = a4
a4.next = a5
s= Solution()
print(s.removeNthFromEnd_opt(a1,2))